#ifndef STX_ALGORITHM_COMMON_HPP
#define STX_ALGORITHM_COMMON_HPP

//  todo: implement <utility>

#include <stx/core.hpp>
#include <cstddef> // std::size_t
#include <iterator>
#include <utility>
#include <climits>
#include <stx/algorithm/advance.hpp>
#include <stx/algorithm/distance.hpp>
#include <stx/algorithm/begin.hpp>
#include <stx/algorithm/end.hpp>
#include <stx/algorithm/range.hpp>
#include <stx/algorithm/swap.hpp>

#define STX_UNROLL_LOOPS 0

namespace stx {

struct destruct_n
{
private:
    
    size_t size;
    
    template <class T>
    void process(T* p, false_type)
    {
        for (size_t i = 0; i < size; ++i, ++p) {
            p->~T();
        }
    }
    
    template <class T>
    void process(T*, true_type)
    {
    }
    
    void incr(false_type)
    {
        ++size;
    }
    
    void incr(true_type)
    {
    }

    void set(size_t s, false_type)
    {
        size = s;
    }
    
    void set(size_t, true_type)
    {
    }
    
public:
    
    explicit destruct_n(size_t s): size(s)
    {
    }
    
    template <class T>
    void incr(T*)
    {
        incr(integral_constant<bool, is_trivially_destructible<T>::value>());
    }
    
    template <class T>
    void set(size_t s, T*)
    {
        set(s, integral_constant<bool, is_trivially_destructible<T>::value>());
    }
    
    template <class T>
    void operator()(T* p)
    {
        process(p, integral_constant<bool, is_trivially_destructible<T>::value>());
    }
};

template <class T>
inline std::pair<T*, std::ptrdiff_t>
get_temporary_buffer(std::ptrdiff_t n) STX_NOEXCEPT
{
    std::pair<T*, std::ptrdiff_t> r(0, 0);
    const std::ptrdiff_t m =
        (~std::ptrdiff_t(0) ^ std::ptrdiff_t(std::ptrdiff_t(1) << (sizeof(std::ptrdiff_t) * CHAR_BIT - 1))) / sizeof(T);
    if (n > m) {
        n = m;
    }
    while (n > 0) {
        r.first = static_cast<T*>(::operator new(n * sizeof(T), std::nothrow));
        if (r.first) {
            r.second = n;
            break;
        }
        n /= 2;
    }
    return r;
}

template <class T>
inline void
return_temporary_buffer(T* p) STX_NOEXCEPT
{
    ::operator delete(p);
}

struct return_temporary_buffer_impl
{
    template <class T>
    void operator()(T* p) const
    {
        return_temporary_buffer(p);
    }
};

template <class Iterator>
inline typename std::iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&)
{
    typename std::iterator_traits<Iterator>::iterator_category category;
    return category;
}

template <class T1, class T2 = T1>
struct equal_to
{
    bool operator()(const T1& x, const T1& y) const { return x == y; }
    bool operator()(const T1& x, const T2& y) const { return x == y; }
    bool operator()(const T2& x, const T1& y) const { return x == y; }
    bool operator()(const T2& x, const T2& y) const { return x == y; }
};

template <class T1>
struct equal_to<T1, T1>
{
    bool operator()(const T1& x, const T1& y) const { return x == y; }
};

template <class T1>
struct equal_to<const T1, T1>
{
    bool operator()(const T1& x, const T1& y) const { return x == y; }
};

template <class T1>
struct equal_to<T1, const T1>
{
    bool operator()(const T1& x, const T1& y) const { return x == y; }
};

template <class T1, class T2 = T1>
struct less
{
    bool operator()(const T1& x, const T1& y) const { return x< y; }
    bool operator()(const T1& x, const T2& y) const { return x< y; }
    bool operator()(const T2& x, const T1& y) const { return x< y; }
    bool operator()(const T2& x, const T2& y) const { return x< y; }
};

template <class T1>
struct less<T1, T1>
{
    bool operator()(const T1& x, const T1& y) const { return x< y; }
};

template <class T1>
struct less<const T1, T1>
{
    bool operator()(const T1& x, const T1& y) const { return x< y; }
};

template <class T1>
struct less<T1, const T1>
{
    bool operator()(const T1& x, const T1& y) const { return x< y; }
};

template <class Predicate>
class negate
{
public:
    negate() {}
    
    explicit negate(Predicate p) : p_(p) {}
    
    template <class T1>
    bool operator()(const T1& x) {return !p_(x);}
    
    template <class T1, class T2>
    bool operator()(const T1& x, const T2& y) {return !p_(x, y);}
    
private:
    Predicate p_;
};

} // namespace stx

#endif // STX_ALGORITHM_COMMON_HPP
